One of the problems that the invention seeks to resolve is to guarantee the real-time feasibility of the implementation of a set of multi-frame tasks, which together define an application or a system, having given execution time, deadline and guard time parameters on a given processor. To this end, the technical problem to be resolved relates to the real-time scheduling of these tasks on this processor. In order to guarantee that the design of the software tasks is valid for a real-time implementation, it is necessary to test whether the time limits are never exceeded by checking notably that each task is executed well before its deadline. The resolution of this technical problem makes it possible to validate the correct operation of the scheduler which is implemented by the operating system associated with the processor.
A scheduler is a component of the operating system whose function is to determine the order in which the tasks or processes will be executed on a processor so as to observe the real-time constraint. The use of a scheduler makes it possible to execute a number of tasks or processes in parallel on a single processor by sharing its resources in time. In this way, the real-time execution of the tasks is possible. However, there are cases in which the specification of the software tasks to be executed is such that it does not allow for their simultaneous real-time execution, and in this case the scheduler cannot operate correctly because it will be required to resolve a problem which has no solution. These solutions are not necessarily easy to detect and avoid, notably in the case of complex applications which use a number of concurrent tasks which are themselves executing a processing operation on a number of data frames having execution constraints that are bounded in time. It is therefore important to be able to detect these cases during the design phase of the overall architecture of the system in order to redefine the parameters of the software tasks that are to be deployed on a given processor if said tasks are not compatible with a real-time execution.
One scheduling policy known to those skilled in the art is the dynamic priority scheduling method, known by the abbreviation EDF (Earliest Deadline First). This method consists in assigning a dynamic priority to each task or process according to the deadline thereof. The nearer the deadline of a task, the higher its priority. The invention is positioned notably in the context of this scheduling method.
The document [1] describes the concept of multi-frame tasks and proposes modeling a set of real-time software tasks using this concept. A multi-frame task is a task or software function which executes a processing operation on a plurality of data frames characterized by the three parameters of execution time E, deadline D and guard time P introduced previously in this document, and for which, in addition, the execution time E is variable from one frame to another.
The document [2] reprises this concept, generalizing it to a set of multi-frame tasks for which the deadline D and the guard time P are also variable. A feasibility test associated with a dynamic priority scheduling method (such as the EDF method) is proposed in the document [2]. This method is based on the construction of a bounded requirement function dependent on the parameters E, D and P and that makes it possible to validate the feasibility of the real-time execution of a plurality of software tasks on a given processor.
The solution proposed by the document [2] is limited to the particular case in which there is a periodicity, also called cycle, in the successive call to the tasks and the time sequencing of the processing of the frames. In this case, it is possible to find a repetition pattern which entirely defines the time sequencing of the execution of a task over a given period of time. An example of such a case is described in FIG. 1. A software task i which executes a processing operation on three different types of data frames, each characterized by the three parameters that are execution time Ci1, Ci2, Ci3, deadline Di1, Di2, Di3 between the instant when the task is activated and the instant when it needs to have terminated the processing of the frame to observe the real-time constraints and guard time Pi1, Pi2, Pi3 between two successive calls to this task. At the end of a cycle time T=Pi1+Pi2+Pi2, the time execution pattern of the task i is repeated periodically as illustrated in FIG. 1. The task i is then qualified as a cyclic multi-frame task.
Such a case corresponds, for example, to the case of a video compression device of MPEG (Motion Picture Expert Group) type which can manipulate three types of different data frames known to those skilled in the art by the frame identifier I, P or B, and which are transmitted more often than not according to a cyclic time pattern.
The requirement function introduced in [2] and that makes it possible to test the feasibility of a set of multi-frame tasks, uses the period or cycle T to resolve the problem of scheduling of the tasks and is therefore limited to the case of cyclic tasks.